\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 9}}
\end{center}

\noindent{\textbf{Exercise 9.1}}\\
a)\\
S $\rightarrow$ $Q_0$\\
$Q_0$ $\rightarrow$ 0$Q_1$ $\mid$ 1$Q_0$\\
$Q_1$  $\rightarrow$ 1$Q_0$ $\mid$ 0$Q_2$\\
$Q_2$ $\rightarrow$ $\epsilon$ $\mid$ 0$Q_2$ $\mid$ 1$Q_0$\\
b)\\
A grammar is ambiguous if it creates the same string in different ways. For the given grammar we can either ``introduce  b'' by using the second rule or first pump in a's. Take for example the string: abaab. So following sequences (leftmose derivations) are both possible using the given grammar:\\
S $\rightarrow$ aSbS $\rightarrow$ abS $\rightarrow$ abaSbS $\rightarrow$ abaaSbS $\rightarrow$ abaabS $\rightarrow$ abaab\\
S $\rightarrow$ aSbS $\rightarrow$ abS $\rightarrow$ abaS $\rightarrow$ abaaSbS $\rightarrow$ abaabS $\rightarrow$ abaab\\
c)\\
Given G, we generate the CNF as follows:\\
\begin{enumerate}
\item First, we introduce a new start symbol S$_{0}$:\\
S$_{0}$ $\rightarrow$ S\\
S $\rightarrow$ XY\\
X $\rightarrow$ abb $\mid$ aXb $\mid$ $\epsilon$\\
Y $\rightarrow$ c $\mid$ cY\\
\item We remove all rules A$\rightarrow$  $\epsilon$ (X $\rightarrow$  $\epsilon$):\\
S$_{0}$ $\rightarrow$ S\\
S $\rightarrow$ XY $\mid$ Y\\
X $\rightarrow$ abb $\mid$ aXb $\mid$ ab\\
Y $\rightarrow$ c $\mid$ cY\\
\item We remove all unit rules A$\rightarrow$ B (S$_{0}$ $\rightarrow$ S and S$_{0}$ $\rightarrow$ Y):\\
S$_{0}$ $\rightarrow$ XY $\mid$ Y\\
X $\rightarrow$ abb $\mid$ aXb $\mid$ ab\\
Y $\rightarrow$ c $\mid$ cY\\
\\
S$_{0}$ $\rightarrow$ XY $\mid$ c $\mid$ cY \\
X $\rightarrow$ abb $\mid$ aXb $\mid$ ab\\
Y $\rightarrow$ c $\mid$ cY\\
\item
\begin{enumerate}
\item Convert remaining rules A $\rightarrow$ u$_{1}$u$_{2}$ ... u$_{k}$, where k$\geq$3, into rules A $\rightarrow$ u$_{i}$A$_{j}$, creating new variables A$_{j}$:\\
S$_{0}$ $\rightarrow$ XY $\mid$ c $\mid$ cY \\
X $\rightarrow$ aR $\mid$ Tb $\mid$ ab\\
Y $\rightarrow$ c $\mid$ cY\\
R $\rightarrow$ bb\\
T $\rightarrow$ aX\\
\item Case K=2:\\
S$_{0}$ $\rightarrow$ XY $\mid$ c $\mid$ UY \\
X $\rightarrow$ VR $\mid$ TW $\mid$ VW\\
Y $\rightarrow$ c $\mid$ UY\\
R $\rightarrow$ WW\\
T $\rightarrow$ VX\\
U $\rightarrow$ c\\
V $\rightarrow$ a\\
W $\rightarrow$ b\\

\end{enumerate}

\end{enumerate}

\vspace{1cm}
\noindent{\textbf{Exercise 9.2}}\\\\
a)\\
(aaadbabacc, $q_0$, $\epsilon$)\\
(aaadbabacc, $q_1$, \$)\\
(aadbabacc, $q_1$, x\$)\\
(aadbabacc, $q_2$, x\$)\\
(adbabacc, $q_2$, yx\$)\\
(dbabacc, $q_2$, yyx\$)\\
(babacc, $q_3$, yyx\$)\\
(abacc, $q_4$, yyx\$)\\
(bacc, $q_3$, yx\$)\\
(acc, $q_4$, yx\$)\\
(cc, $q_3$, x\$)\\
(cc, $q_5$, x\$)\\
(c, $q_6$, x\$)\\
($\epsilon$, $q_5$, \$)\\
($\epsilon$, $q_5$, $\epsilon$)\\
accept\\
\\b)
It acepts the language L = \{$a^ia^jd(ba)^kc^l \mid j=k$ and $i=l$\}


\newpage
\noindent{\textbf{Exercise 9.3}}\\
The following PDA recognizes the language L = \{a$^{i}$b$^{j}$c$^{k}$ $\mid$  i = j or j = k\}:\\
\begin{center}
\includegraphics[width=1\textwidth]{exercise9_3-PDA.pdf}
\end{center}

\end{document}

